package cn.bellychang.leetcode.question232;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * Implement a first in first out (FIFO) queue using only two stacks.
 * The implemented queue should support all the functions of a normal queue (push, peek, pop, and empty).
 * <p>
 * <p>
 * <p>
 * notes:
 * 1. You must use only standard operations of a stack, which means only push to top, peek/pop from top, size, and is empty operations are valid.
 * 2. Depending on your language, the stack may not be supported natively.
 * You may simulate a stack using a list or deque (double-ended queue) as long as you use only a stack's standard operations.
 * <p>
 * Follow-up:
 * Can you implement the queue such that each operation is amortized O(1) time complexity?
 * In other words, performing n operations will take overall O(n) time even if one of those operations may take longer.
 *
 * @author ChangLiang
 * @date 2021/1/28
 */
public class MyQueue {

    private Deque<Integer> stackA;
    private Deque<Integer> stackB;
    int count;

    /**
     * Initialize your data structure here.
     */
    public MyQueue() {
        stackA = new ArrayDeque<>();
        stackB = new ArrayDeque<>();
        count = 0;
    }

    /**
     * Push element x to the back of queue.
     */
    public void push(int x) {
        if (count == 0) {
            stackA.push(x);
        } else {
            for (int i = 1; i <= count; i++) {
                Integer pop = stackA.pop();
                stackB.push(pop);
            }
            stackA.push(x);
            for (int i = 1; i <= count; i++) {
                stackA.push(stackB.pop());
            }
        }
        count++;
    }

    /**
     * Removes the element from in front of queue and returns that element.
     */
    public int pop() {
        count--;
        return stackA.pop();
    }

    /**
     * Get the front element.
     */
    public int peek() {
        return stackA.peek();
    }

    /**
     * Returns whether the queue is empty.
     */
    public boolean empty() {
        return count == 0;
    }

    @Override
    public String toString() {
        StringBuilder builder = new StringBuilder();
        int[] temp = new int[count];
        int index = count - 1;
        for (int i = 0; i < count; i++) {
            // 弹出来
            temp[index] = stackA.pop();
            index--;
        }
        for (int i = 0; i < count; i++) {
            builder.append(temp[i]).append("->");
            // 补偿回来
            stackA.push(temp[i]);
        }
        return builder.toString().endsWith("->") ?
                builder.toString().substring(0, builder.length() - 2) :
                builder.toString();
    }
}
